// Growth-rate calculator.

// Antitidictionary stores the set of forbidden words in a language.
// Subclasses define the actual algorithm of building this set.

#ifndef GRATE_ANTIDICTIONARY_H
#define GRATE_ANTIDICTIONARY_H

#include "dfa.h"

namespace growth_rate {

class LexminAntiDictionary {
 public:
  virtual ~LexminAntiDictionary() {
    CHECK_EQ(0, trie_);
  }

  // Builds new LexminTrie and returns it to the caller, who owns it.
  LexminTrie *build_trie() {
    CHECK_EQ(0, trie_);
    trie_ = new LexminTrie(trie_capacity_, alphabet_size_);
    CHECK(construct());
    LexminTrie *result = trie_;
    trie_ = 0;
    return result;
  }

  // Returns the memory usage (in bytes) used for building a trie
  // of forbidden words so far. This doesn't include memory allocated
  // to store a trie itself.
  virtual size_t extra_memory_usage() const {
    return 0;
  }

 protected:
  LexminAntiDictionary(size_t trie_capacity, uint8_t alphabet_size)
    : trie_(0),
      trie_capacity_(trie_capacity),
      alphabet_size_(alphabet_size) { }

  bool add_lexmin_word(const Word &word) {
    CHECK(trie_);
    return trie_->add_lexmin_word(word);
  }
  bool trie_accepts_word(const Word &word, Direction direction) const {
    CHECK(trie_);
    return trie_->accepts_word(word, direction);
  }
  bool has_factor_forbidden_by_trie(const Word &word) const {
    CHECK(trie_);
    if (word.length() == 0) return false;
    // Check all proper suffixes.
    for (size_t i = 1; i < word.length(); i++) {
      if (!trie_accepts_word(word.suffix(i), Forward))
        return true;
    }
    // Check largest proper prefix.
    return (!trie_accepts_word(word.prefix(word.length() - 1), Forward));
  }


 private:
  // Constructs antidictionary and stores it in the trie. Returns true
  // if construction was successful. Subclasses should implement this
  // function.
  virtual bool construct() = 0;

  LexminTrie *trie_;  // Trie of forbidden words. It should be filled with
                      // words in construct() function of subclasses.
  const size_t trie_capacity_;
  const uint8_t alphabet_size_;
};

}  // namespace growth_rate

#endif  // GRATE_ANTIDICTIONARY_H
